1. Field of the Invention
The present invention relates to a pattern data generating system for generating pattern data in which an arbitrary closed graphic pattern whose boundary data is defined on a two-dimensional bit map is filled or painted.
2. Description of the Prior Art
In the field of graphics, it is often required to form pattern data by filling or painting an area defined by an polygonal boundary. It is also required to sequentially generate points, one by one, for forming an arbitrary curve and to fill or paint a portion surrounded by the curve, using hardware such as a DDA (digital differential analyzer). In a conventional system, in order to satisfy such requirements, filling or painting is performed by a scan conversion for polygons. According to the scan conversion, one direction on a two-dimensional bit map is selected. The selected direction is called a scan direction. A line parallel to the scan direction is called a scan line. When filling or painting is to be performed, the coordinates of both ends of a line, included in a closed graphic pattern, are obtained for each scan line, and all lines in the pattern are filled or painted, thereby painting the overall graphic pattern.
A conventional filling/painting operation of a polygon using the scan conversion will be described with reference to FIGS. 10 and 11A to 11C. Referring to FIG. 10, reference numeral 71 denotes a rectangular area to be scan-converted; 72 to 77, vertexes of the boundaries of a polygon; 78 to 83, sides of the polygon; and 91, one scan line.
Procedure (1): Intersection points P0, P1, P2, and P3 of one scan line 91 and sides of the polygon are obtained. Then, the intersection points are sorted in the order of the coordinate values in the scan direction.
Procedure (2): If a given intersection point is an end of a side, i.e., a vertex of the polygon, the give intersection point is processed in accordance with a connection state of the sides of the polygon. In the case shown in FIG. 11A, for example, vertex A is processed as a normal intersection point. In the case shown in FIG. 11B, one of vertexes B and C is processed as an intersection point. In the case shown in FIG. 11C, vertex D is processed as two intersection points.
Procedure (3): The sorted intersection points are paired, and lines having these pairs as their both ends (lines 84 and 85 in FIG. 10) are filled or painted.
Accordingly, in the conventional system, since software processing, such as sorting, takes a considerably long period of time, high-speed filling/painting cannot be performed. Further, it is practically difficult to achieve the function of the software processing by a hardware system.
In addition, when lines are to be filled or painted, vertexes require special processing, as described in procedure (2). Moreover, even if a change in each point of a curve defining an area is generated in a software manner by using a processor or in a hardware manner by using a DDA or the like, the change in each point need be processed as one line in scan conversion. As a result, a large amount of data must be processed.
As described above, in the conventional system, when painting of a closed graphic pattern is performed, various drawbacks are posed, e.g., high-speed processing cannot be performed, and a hardware system is difficult to arrange.